In a distributed storage system, values may be written to and stored across a plurality of nodes. When consecutive read requests for a key with no intervening writes are received, the same value should be returned. However, in some instances, one or more nodes of the distributed system may go offline and online sporadically during a write operation. As a result, it is possible that various read requests to the same value that has not changed may return inconsistent values depending on the timing of the request at various different failure states of the nodes. Maintaining read-after-read consistency of a value is important in many applications.